package lhc.alg.top100;

import java.util.Arrays;

/**
 * description: https://leetcode.cn/problems/intersection-of-two-arrays/
 * 两个数组的交集 可以直接api解法
 *
 * public int[] intersection(int[] nums1, int[] nums2) {
 *     Set<Integer> set = Arrays.stream(nums1).boxed().collect(Collectors.toSet());
 *     return Arrays.stream(nums2).distinct().filter(set::contains).toArray();
 * }
 *
 * 方法一: 放到两个set 小的遍历大的
 * 方法二：排序+双指针（此方法）
 *
 * O(mlogm + nlogn)
 * O(logm + logn)
 *
 * author: hongchen.liao
 * date:  2022/8/29
 */
public class _349_Intersection_of_Two_Arrays {

    class Solution {
        public int[] intersection(int[] nums1, int[] nums2) {
            Arrays.sort(nums1);
            Arrays.sort(nums2);
            int len1 = nums1.length, len2 = nums2.length;
            int[] res = new int[len1+len2];
            int index = 0, index1 = 0, index2 = 0;
            while(index1 < len1 && index2 < len2){
                int i = nums1[index1], j = nums2[index2];
                if(i == j){
                    if(index == 0 || res[index-1] != i){
                        res[index++] = i;
                    }
                    index1++;
                    index2++;
                }else if(i < j){
                    index1++;
                }else{
                    index2++;
                }
            }
            return Arrays.copyOfRange(res, 0, index);
        }
    }

}
